package cn.jdemo.algorithm.hard;

/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *
 * trap(i) = min(lmax,rmax) - height(i);
 *
 *
 * 双指针
 * * left: trap(left) = 当lmax<rmax时
 * * lmax = height[0..left]
 * * right: trap(right) = 当lmax<=rmax时
 * * rmax = height[right...end]
 *
 * int res = 0;
 * if(lmax < rmax){
 *      res += lmax - height(left)
 * }else{
 *      res += rmax - height(right)
 * }
 */
public class Trap2 {
    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        int trap = new Trap2().trap(height);
        System.out.println(trap);
    }

    public int trap(int[] height) {
        int res = 0;
        int length = height.length;
        int left =0,right =length-1;
        int lmax = height[0];
        int rmax = height[right];

        while (left <= right){
            lmax = Math.max(lmax, height[left]);
            rmax = Math.max(rmax, height[right]);
            if (lmax < rmax){
                res += lmax - height[left];
                left++;
            }else{
                res += rmax - height[right];
                right--;
            }
        }
        return res;
    }

}
